It is well known to construct an asynchronous first-in first-out (FIFO) buffer using a comparator technique that uses counters, adders and combinatorial logic to generate a half-full flag indicating the FIFO is half-full. A typical FIFO has both a read and write pointer. The difference between the read and write pointers is computed using an adder and the final half-full flag is generated by performing a magnitude comparison of the adder output with the binary value of FIFO.sub.-- SIZE/2. A second alternate technique, an evaluation technique, can be used for generating the half-full flag and is implemented by evaluating the expression write.sub.-- count-read.sub.-- count-1. The evaluation technique uses the logic state of the bit corresponding to the half-full position(MSB-1'th bit) to represent the half-full flag. A third alternate technique for generating the half-full flag can be implemented by using direct decode logic where an internal half-full and half-full+1 signals are directly decoded from the counters. The half-full (HF) and half-full plus one (HF+1) signals drive set-reset (SR) latch. The output of the SR latch represents the half-full flag.
In the comparator technique, there are two counters, one each for the read and write clocks. These two counters are reset to zero upon master reset and are incremented based on only their respective clocks. The outputs of the read and write counters are fed into a subtractor that calculates the difference between the number of locations written to the FIFO and the number of locations read from the FIFO. This difference is then compared to the magnitude of the binary value representing the half-full count. The output of the magnitude comparator is the half-full flag.
In any FIFO, the write.sub.-- count-read.sub.-- count is always less than or equal to the size of the FIFO. This scheme takes advantage of this fact and in the adder stage a 1 is additionally subtracted. From the result of this subtraction the bit value corresponding to the half-full position (MSB-1'th bit) is used with a logic inversion to represent the external half-full flag.
The direct decode technique generates the half-full flag by decoding a write half-full signal when the FIFO is exactly half-full and a read half-full signal when the FIFO is exactly half-full plus one. The write half-full signal and the read half-full signal, together with logic associated to the reset and retransmit functions, set and reset a latch. The output of the latch generates the half-full flag. Even though the direct decode technique is relatively faster (delays in the magnitude of 15-20 ns) than the comparator technique or the evaluation technique, the direct decode technique suffers from metastability deficiencies and requires fine glitch filters at the input of the latch. Also, the delay in producing the half-full flag is directly related to the density of the FIFO.
The comparator technique and the evaluation technique suffer from long flag delays, while the direct decode technique suffers from metastability deficiencies as well as intensive design requirements. The present invention solves all the problems associated with the various prior art techniques by providing a half-full flag having very high MTBF and very short delays. Additionally the delay associated in producing the half-full flag is independent of the size of the FIFO.